package algorithm;


import com.sun.java.swing.plaf.windows.WindowsTableHeaderUI;
import com.sun.org.apache.xpath.internal.WhitespaceStrippingElementMatcher;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;

//贪心算法解决集合覆盖问题
public class Greedy {
    public static void main(String[] args) {

        HashMap<String, HashSet<String>> map = new HashMap<>();
        HashSet<String> set1 = new HashSet<>();
        set1.add("北京");
        set1.add("上海");
        set1.add("天津");

        HashSet<String> set2 = new HashSet<>();
        set2.add("广州");
        set2.add("北京");
        set2.add("深圳");

        HashSet<String> set3 = new HashSet<>();
        set3.add("成都");
        set3.add("上海");
        set3.add("杭州");


        HashSet<String> set4 = new HashSet<>();
        set4.add("天津");
        set4.add("上海");

        HashSet<String> set5 = new HashSet<>();
        set5.add("杭州");
        set5.add("大连");

        map.put("k1", set1);
        map.put("k2", set2);
        map.put("k3", set3);
        map.put("k4", set4);
        map.put("k5", set5);

        HashSet<String> allAreas = new HashSet<>();
        allAreas.addAll(set1);
        allAreas.addAll(set2);
        allAreas.addAll(set3);
        allAreas.addAll(set4);
        allAreas.addAll(set5);
        System.out.println("所有地区" + allAreas);

        HashSet<String> tempSet = new HashSet<>();
        //maxKey 保存在一次遍历过程中，能够覆盖最大未覆盖的地区对应的key
        ArrayList<String> selects = new ArrayList<>();
        String maxKey = null;
        while (allAreas.size() != 0) {
            maxKey = null;
            for (String key : map.keySet()) {
                tempSet.clear();
                HashSet<String> areas = map.get(key);
                tempSet.addAll(areas);
                tempSet.retainAll(allAreas);
                if (tempSet.size() > 0 &&
                        (maxKey == null || tempSet.size() > map.get(maxKey).size())) {
                    maxKey = key;
                }
            }
            if (maxKey != null) {
                selects.add(maxKey);
                allAreas.removeAll(map.get(maxKey));
            }
        }
        System.out.println("选择的结果" + selects);
    }
}
